洛谷 P3916 图的遍历 题解

发表于 | 分类于 | | 热度: ℃

Description

给出 $n$ 个点，$m$ 条边的有向图，对于每个点 $v$，求 $A(v)$ 表示从点 $v$ 出发，能到达的编号最大的点。

数据范围：$1<=n,m<=10^5$

Solution

建边的时候建反向边。从编号最大的点开始，搜索其能够到达的所有 未标记 的点，将这些点标记。同时将这些点的答案记为当前点的编号。时间复杂度为 $O(n)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 200006;
struct edge
{
    int nxt, to;
} e[N];
int n, m, a, b, cnt = 0, head[N], ans[N], vis[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return x * f;
}

void add(int x, int y)
{
    e[++cnt] = (edge) { head[x], y };
    head[x] = cnt;
}

void bfs(int x)
{
    queue <int> q;
    q.push(x);
    vis[x] = 1;
    while(!q.empty())
    {
        int a = q.front();
        q.pop();
        ans[a] = x;
        for(int i = head[a]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if(!vis[v]) { vis[v] = 1; q.push(v); }
        }
    }
}

int main()
{
    n = read(), m = read();
    for(int i = 1; i <= m; i++)
    {
        a = read(), b = read();
        add(b, a);
    }
    memset(vis, 0, sizeof(vis));
    for(int i = n; i > 0; i--)
    {
        if(vis[i]) continue;
        bfs(i);
    }
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
    return 0;
}